Die Burg in Mytilini, der Inselhauptstadt von Lesbos, zählte zu den größten Festungsanlagen im östlichen Mittelmeer. Sie liegt zwischen dem nördlichen und südlichen Hafen von Mytilini auf einem mit Kiefern bewachsenen Hügel. Die Festung gliedert sich in drei Ebenen. Auf der Hügelspitze errichteten etwa im 6. Jh. die Byzantiner auf den Resten einer antiken Akropolis die obere Burg.
Aus dieser Zeit sind sich noch ein Tor an der Nordseite, Befestigungsbauten an der Ostmauer sowie die Zisterne auf dem zentralen Gelände der Festung erhalten geblieben. Wesentliche Ausbauten und der Bau der mittleren Ebene der Festung gehen auf die genuesische Familie Gattilusio zurück, die Lesbos im Jahr 1355 von dem byzantinischen Kaiser Johannes V. als Lehen erhielt.
Einer lateinischen Inschrift am Westtor zufolge wurden die Um- und Ausbauten im Jahr 1373 begonnen. 1384 richtete ein verheerendes Erdbeben große Schäden an. Während der Zeit von Domenico und Niccolo Gattilusio wurden die Mauern und Wälle verstärkt, Gräben angelegt, Zinnen errichtet und weitere Kanonen angeschafft. Durch Verrat eroberten die Osmanen nach einer Belagerung 1462 die Festung von Mytilini.
Die osmanischen Sultane erbauten den unteren, dritten Teil der Festung und ließen zwei zusätzliche Geschütztürme errichten. Weitere Ausbauarbeiten erfolgten 1643 – 1644. Aus dieser Zeit stammen die meisten Gebäude innerhalb der Mauern. Heute sind in der Festung noch der zentrale Westturm, die Kulé-Moschee, ein osmanisches Tor, eine islamische Priesterschule sowie Zisternen und unterirdische Hallen zu sehen.
